Metode numerice - Aplicatii

Lucrarea 9.   Ecuatii neliniare: accelerarea convergentei metodelor de ordin I - Metoda falsei pozitii si metoda Aitken

Tema A - Metoda falsei pozitii           <----------- algoritm
Tema B - Metoda Aitken                    <----------- algoritm

     In aplicatiile practice intereseaza, desigur, asigurarea unei convergente cat mai rapide a procesului iterativ care construieste sirul aproximatiilor succesive. In limbajul calculului numeric, accelerarea convergentei inseamna aplicarea unor metode cu ordin de convergenta cat mai mare. Dintre metodele prezentate in paragrafele anterioare, cele mai bune performante din acest punct de vedere le are metoda Newton, caracterizata de convergenta patratica. Metodele de partitionare (metodele bisectiei, a secantei sau a cautarii cu pas variabil) sau metoda contractiei intra in categoria metodelor de ordin I. Diferitele variante ale metodei Newton se caracterizeaza, in general, prin reducerea ratei de convergenta: metoda Traub asigura doar o convergenta superliniara, in timp ce metoda Newton simplificata coboara pana la convergenta liniara. Exceptia o reprezinta metoda Bailey, care folosind si derivata de ordin doi calculata analitic, ajunge la o convergenta superpatratica, fara a atinge insa ordinul III. Mai trebuie spus ca, de regula, cresterea ordinului de convergenta este insotita de amplificarea volumului de calcule efectuate la fiecare iteratie. Daca vrem ca metoda folosita sa fie eficienta din punct de vedere numeric trebuie sa mentinem aceasta balanta cat mai aproape de echilibru. In fond, interesul final este un timp de calcul cat mai redus, adica un numar mic de iteratii, dar si un timp de calcul pe iteratie redus.
     Dintre procedeele de accelerare a convergentei cunoscute, in cele ce urmeaza vom descrie succint metoda falsei pozitii si metoda Aitken.

Tema A - Metoda falsei pozitii

     Metoda falsei pozitii reprezinta un caz particular al metodei Newton. Ca procedeu de accelerare, ea nu trebuie raportata insa la metoda Newton, pe care dealtfel o "franeaza", ci la metodele de ordin intai, fata de care ofera convergenta superliniara. Modelul matematic porneste de la formula de iterare a metodei Newton:

si de la ipoteza ca nu se dispune de expresia analitica a functiei f(x), ceea ce nu permite calculul exact al derivatei f'(x_n). Pentru a utiliza totusi o relatie de aceasta forma derivata f'(x_n) poate fi evaluata cu ajutorul formulei aproximative:
astfel incat noua aproximatie x_n+1 se va calcula cu relatia:
care reprezinta formula de iterare a metodei falsei pozitii. Avem de-a face, de aceasta data, cu o formula de iterare de ordin 2, deoarece aproximatia x_n+1 se calculeaza in functie de doua aproximatii anterioare x_n si x_n-1.
     Metodei falsei pozitii i se poate asocia o interpretare geometrica care face mai "transparent" suportul matematic descris. Astfel (vezi figura alaturata), pornind de la aproximatiile x_n si x_n-1, tangenta in punctul x_n este aproximata prin dreapta ce trece prin punctele n-1 si n, iar noua aproximatie x_n+1 corespunde intersectiei acestei drepte cu axa absciselor. In figura se indica si o comparatie intre metoda Newton si metoda falsei pozitii, sugerandu-ne si raspunsul la intrebarea: cat de mult se abate x_n+1 fata de x'_n+1 (aproximatia calculata cu formula Newton) ? Cu cat curbura functiei f(x) intre punctele n-1 si n este mai mare, cu atat aproximatia x_n+1 se va abate mai mult fata de valoarea calculata cu formula de iterare a metodei Newton. Altfel spus, rata de convergenta a metodei falsei pozitii este cu atat mai mare cu cat, in aproximatia curenta x_n, functia f(x) are o derivata de ordin doi f"(x_n) mai mica in valoare absoluta.
     Daca se compara formulele de iterare ale metodelor falsei pozitii si secantei se constata ca se obtin forme similare. Echivalenta celor doua metode este insa numai aparenta: formulele de iterare sunt aceleasi, dar ele se aplica unor puncte diferite de pe curba y=f(x). Metoda falsei pozitii foloseste permanent ultimele doua aproximatii, pe cand metoda secantei, datorita conditiei de incadrare a solutiei exacte, poate impune "uitarea" unor puncte "noi" si inlocuirea lor cu puncte "vechi". In aceasta consta, de fapt, deosebirea esentiala intre cele doua metode si, tot de aici, rezulta proprietatile superioare de convergenta ale metodei falsei pozitii. In timp ce metoda secantei converge liniar, metoda falsei pozitii are o convergenta superliniara; se poate arata ca ordinul acestei metode este. Diferenta intre cele doua metode este ilustrata in figura de mai jos.
     Uneori insa metoda falsei pozitii poate plati un pret "dureros" pentru surplusul de viteza de convergenta pe care il ofera. Pentru functii f(x) "insuficient" de uniforme in apropierea solutiei exacte, noile aproximatii pot fi aruncate in afara intervalului in care fusese izolata initial solutia. Exemplul din figura (b) este un caz fericit, dar putem intalni situatii "patologice" in care aproximatia sa fie aruncata spre infinit.
     O ultima observatie care se impune a fi facuta asupra utilizarii metodei falsei pozitii revine la formula de iterare. Fiind vorba de o formula de iterare de ordin superior unitatii, aplicarea ei necesita folosirea unei metode cu "autopornire" care, pe langa aproximatia initiala x_0, sa puna la dispozitie o aproximatie suplimentara x_1, necesara pentru determinarea lui x_2. Pentru primul pas se poate utiliza orice metoda cu ordin de convergenta inferior, de exemplu metoda secantei. Primul punct intermediar x3 se determina dupa metoda secantei, iar in interiorul buclei iterative aproximatiile succesive se calculeaza folosind direct formula de iterare a metodei falsei pozitii.

Algoritmul 1 - Ecuatii neliniare - Metoda falsei pozitii
  1. Definirea functiei f(x) si a functiei g(x), ultima fiind folosita de catre metoda de pornire.
  2. Definirea preciziei de calcul dorite Eps
  3. Initializarea contorului de iteratii (It <--- 0) si a aproximatiei initiale x(0)
  4. Pornirea algoritmului folosind o metoda de ordin I : x(1) <--- g(x(0))
  5. Aplicarea metodei falsei pozitii:
    1. Trecerea la o noua iteratie: It <--- It+1
    2. Calculul noii aproximatii:
      x(It+1) = ( x(It-1)*f(x(It)) - x(It)*f(x(It-1)) ) / ( f(x(It)) - f(x(It-1)) )
    3. Verificarea conditiei de oprire:
      • Daca | x(It+1) - x(It) | < Eps, precizia impusa a fost atinsa si se trece la pasul 6.
      • Daca | x(It+1) - x(It) | > Eps, procesul iterativ continua prin revenirea la pasul 5.i.
  6. Radacina aproximativa este x(It+1).

Tema B - Metoda Aitken

     Metoda Aitken porneste de la un sir de aproximatii succesive { x_n } convergent liniar si construieste un sir { x'_n } convergent patratic. In principiu, accelerarea Aitken poate fi aplicata oricarui sir de aproximatii generat cu o metoda de ordin I. In continuare vom considera insa o metoda de contractie, ce foloseste formula generala de iterare:

pentru care eroarea de aproximare evolueaza dupa o lege:
unde (e_n) reprezinta eroarea determinata de neglijarea termenilor de rang superior din dezvoltarea in serii Taylor. In ipoteza neglijarii termenului de eroare (e_n), pentru doua iteratii succesive, in care se calculeaza aproximayiile x_n+1 si x_n+2, relatia de mai sus se particularizeaza:
Folosind un procedeu elementar de substitutie, se poate deduce expresia solutiei exacte . Totusi, datorita neglijarii termenilor de eroare, valoarea astfel calculata nu mai este valoarea exacta a solutiei , ci doar o noua aproximatie, in principiu, mai buna:
     Procedeul descris de aceasta formula de iterare, prin care o aproximatie x_n, este recalculata in functie de ea insasi si de alte doua aproximatii care o succed x_n+1 si x_n+2, se numeste accelerare Aitken. Se poate demonstra ca sirul aproximatiilor x'_n astfel construit este convergent patratic, adica incepand cu pasul n metoda Aitken are performante comparabile cu cele ale metodei Newton. Pe de alta parte, in urma accelerarii, aproximatia x'_n este, de regula, superioara aproximatiilor x_n+1 si x_n+2. De aceea, pentru cresterea eficientei urmatorului pas de accelerare se impune rafinarea aproximatiilor x_n+1 si x_n+2. De regula, aceasta se obtine prin recalcularea acestora cu metoda de baza de ordin unu, ce foloseste ca aproximatie initiala pe x'_n. In consecinta, accelerarea nu este un proces continuu, ci discretizat, din trei in trei pasi (vezi figura de mai jos). Aceasta face ca, utilizarea procedeului de accelerare Aitken, in combinatie cu o metoda de ordin unu, sa nu atinga convergenta globala patratica a metodei Newton. In orice caz, insa, metoda rezultata va avea o convergenta superliniara.
Principiul accelerarii Aitken. Pornind de la o aproximatie x_n-1, se determina aproximatia x_n, folosind o metoda de ordin unu, dupa care se intra in bucla de accelerare. Se aplica mai intai doi pasi de ordin unu, pentru calculul aproximatiilor x_n+1 si x_n+2, dupa care se recalculeaza x_n, folosind accelerarea Aitken. Bucla se reia pana la satisfacerea unui criteriu de oprire.

Algoritmul 2 - Ecuatii neliniare - Metoda Aitken
  1. Definirea functiei g(x), si a preciziei de calcul dorite Eps.
  2. Definirea rangului de la care incolo se aplica accelerarea ( r > 0 ).
  3. Initializarea contorului de iteratii (It <--- 0) si a aproximatiei initiale x(0)
  4. Calculul aproximatiilor succesive pana la rangul r+2.
    1. Trecerea la o noua iteratie : It <--- It+1
    2. Calculul noii aproximatii : x(It) = g(x(It-1))
    3. Controlul incheierii algoritmului de pornire:
      • Daca It < r+2 se revine la pasul 4.i.
      • Daca It = r+2, algoritmul de pornire se incheie si se trece la pasul 5.
  5. Aplicarea accelerarii Aitken:
    1. Accelerarea cu formula Aitken :
      x(r) = x(r) - ( x(r+1) - x(r) )^2 / ( x(r+2) - 2*x(r+1) + x(r) )
    2. Recalcularea aproximatiilor de rang r+1 si r+2:
      x(r+1) = g(x(r)) x(r+2) = g(x(r+1))
    3. Verificarea conditiei de oprire:
      • Daca | x(r+2) - x(r+1) | < Eps, precizia impusa a fost atinsa si se trece la pasul 6.
      • Daca | x(r+2) - x(r+1) | > Eps, procesul iterativ continua prin revenirea la pasul 5.i.
  6. Radacina aproximativa este x(r+2)

Pentru detalii suplimenatare privind procedeele de accelerare a convergentei metodelor iterative de rezolvare a ecuatiilor neliniare, se poate consulta cartea "Calcul numeric cu aplicatii in Turbo Pascal".
 

   Aplicatii - Lista lucrarilor de laborator